/*
堆排序是一种基于堆（尤其是最大堆或最小堆）的排序算法。它的核心是利用堆的特性，将数组构建成一个最大堆（或最小堆），然后通过不断交换根节点和最后一个节点，并重新调整堆，来实现排序。

堆排序的关键步骤包括：

堆化：将数组构建成最大堆或最小堆。
排序：每次将堆顶元素与最后一个元素交换，然后调整堆，以确保最大堆或最小堆的特性。


代码解读
heapify：堆化函数，用于将数组中的某个节点调整成最大堆的结构。它递归地确保堆的性质。
heapSort：堆排序函数，首先构建最大堆，然后逐步交换堆顶和最后一个元素，并重新堆化。
主程序：测试堆排序，通过调用 heapSort 对数组进行排序，并输出排序前后的结果。
堆排序的特点
时间复杂度：堆排序的平均和最坏时间复杂度都是 
𝑂(𝑛log𝑛)。
空间复杂度：堆排序的空间复杂度为 
O(1)，因为它不需要额外的临时数组。
不稳定性：堆排序可能会改变相同元素的相对顺序，因此是不稳定的。
堆排序通常用于需要原地排序和不依赖额外空间的场合。它的时间复杂度较低，但由于堆化过程中的不断递归，堆排序可能在某些场合比其他排序算法稍慢。
*/

#include <stdio.h>
#include <stdlib.h>

// 堆化函数，将数组调整为最大堆
void heapify(int arr[], int n, int i) {
    int largest = i;  // 最大元素的索引
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2;  // 右子节点索引

    // 找到最大的元素
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大的不是当前节点，则交换并递归调整
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);  // 递归堆化
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 一次一次交换堆顶和最后一个元素，然后重新堆化
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);  // 重新堆化
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 执行堆排序
    heapSort(arr, size);

    printf("排序后数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


